package com.xsherl.leetcode.solution;

import com.xsherl.leetcode.utils.ArrayUtils;
import com.xsherl.leetcode.utils.PrintUtils;

public class WordSearch {

    /**
     * dfs
     * @param board,word m == board.length
     *                   n = board[i].length
     *                   1 <= m, n <= 6
     *                   1 <= word.length <= 15
     *                   board 和 word 仅由大小写英文字母组成
     */
    public boolean exist(char[][] board, String word) {
        int m = board.length, n = board[0].length;
        boolean[][] visit = new boolean[m][n];
        for (int i = 0; i < m; ++i){
            for(int j = 0; j < n; ++j){
                if (board[i][j] == word.charAt(0) && visit(board, i, j, 0, word, visit)){
                     return true;
                }
            }
        }
        return false;
    }

    private boolean visit(char[][] board, int i, int j, int len, String word, boolean[][] visit){
        if (len >= word.length()){
            return true;
        }
        if (i < 0 || j < 0 || i >= board.length || j >= board[0].length || visit[i][j]){
            return false;
        }
        char c1 = board[i][j];
        char c2 = word.charAt(len);
        if (c1 != c2){
            return false;
        }
        visit[i][j] = true;
        boolean flag = visit(board, i + 1, j, len + 1, word, visit)
                || visit(board, i, j + 1, len + 1, word, visit)
                || visit(board, i - 1, j, len + 1, word, visit)
                || visit(board, i, j - 1, len + 1, word, visit);
        visit[i][j] = false;
        return flag;
    }

    public static void main(String[] args) {
        char[][] board = ArrayUtils.parseArray("" +
                "[[\"A\",\"B\",\"C\",\"E\"],[\"S\",\"F\",\"C\",\"S\"],[\"A\",\"D\",\"E\",\"E\"]]" +
                "", char[].class);
        String word = "ABCB";
        PrintUtils.println(board);
        boolean exist = new WordSearch().exist(board, word);
        System.out.println(exist);
    }
}
